package com.hiwhitley.leetcode.easy;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * Created by hiwhitley on 17-2-13.
 */
public class NextGreaterElement_496 {
    public int[] nextGreaterElement(int[] findNums, int[] nums) {
        for (int i = 0; i < findNums.length; i++) {
            int tmp = -1;
            for (int j = nums.length - 1; j != 0; j--) {
                if (nums[j] == findNums[i]) {
                    break;
                }
                if (nums[j] > findNums[i])
                    tmp = nums[j];
            }
            findNums[i] = tmp;
        }

        return findNums;
    }

    public int[] nextGreaterElement2(int[] findNums, int[] nums) {
        Map<Integer, Integer> map = new HashMap<>(); // map from x to next greater element of x
        Stack<Integer> stack = new Stack<>();
        for (int num : nums) {
            while (!stack.isEmpty() && stack.peek() < num)
                map.put(stack.pop(), num);
            stack.push(num);
        }
        for (int i = 0; i < findNums.length; i++)
            findNums[i] = map.getOrDefault(findNums[i], -1);
        return findNums;
    }

    public static void main(String[] args) {
        NextGreaterElement_496 main = new NextGreaterElement_496();
        main.nextGreaterElement(new int[]{4, 1, 2}, new int[]{1, 3, 4, 2});
    }
}
